package com.banmao.CarlCamp.Day08;

import com.alibaba.fastjson.JSON;

/**
 * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
 */
public class LC28 {

    // KMP 算法，忘了
    public int strStr(String haystack, String needle) {

        if (needle.length() == 0) {
            return 0;
        }

        int[] next = getNext(needle.toCharArray());

        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (haystack.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            if (j == needle.length() - 1) {
                return (i - needle.length() + 1);
            }
        }

        return -1;
    }

    private int[] getNext(char[] needleChars) {

        // 生成 next 数组
        int[] next = new int[needleChars.length];
        // 1. 初始化
        // j 指向前缀的尾字符
        int j = -1;
        next[0] = j;
        // i 指向后缀的尾字符，从 1 开始
        for (int i = 1; i < needleChars.length; i++) {
            // 2. 处理前后缀不相同的情况
            while (j >= 0 && needleChars[i] != needleChars[j + 1]) {
                j = next[j];
            }
            // 3. 处理前后缀相同的情况
            if (needleChars[i] == needleChars[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static void main(String[] args) {
        LC28 lc28 = new LC28();

        //int res = lc28.strStr("aadbutsad", "sad");
        //System.out.println(res);

        System.out.println(JSON.toJSONString(lc28.getNext("aabaaf".toCharArray())));

    }

}
